A Comparative Study of Efficient Initialization Methods for the K-Means Clustering Algorithm

摘要

K-means is undoubtedly the most widely used partitional clustering algorithm.Unfortunately, due to its gradient descent nature, this algorithm is highlysensitive to the initial placement of the cluster centers. Numerousinitialization methods have been proposed to address this problem. In thispaper, we first present an overview of these methods with an emphasis on theircomputational efficiency. We then compare eight commonly used linear timecomplexity initialization methods on a large and diverse collection of datasets using various performance criteria. Finally, we analyze the experimentalresults using non-parametric statistical tests and provide recommendations forpractitioners. We demonstrate that popular initialization methods often performpoorly and that there are in fact strong alternatives to these methods.